package com.thread;

import java.math.BigDecimal;
import java.util.Arrays;

public class Main {
    // Arrays.sort(arr);
    static int[] flag = new int[100];
    static int index = 0;// 记录当前
    public Main() {
    }
    public static int formatDoubleTOInt(double dou1,double dou2){
        BigDecimal big1 = new BigDecimal(Double.valueOf(dou1)).setScale(2, BigDecimal.ROUND_HALF_UP);
        BigDecimal big2 = new BigDecimal(Double.valueOf(dou2));
        return big1.multiply(big2).intValue();

    }

    public static void numGroup(int[] arr, int start, int length, int sum) {
        if (sum == 0) {
            for (int j = 0; j < index; j++) {
                System.out.print((double)(flag[j])/100+"+");
            }
            System.out.println();
        }
        else if(sum>0) {
            for (int i = start; i < length; i++) {
                int temp_sum=sum - arr[i];

                if(temp_sum>=0)
                {
                    flag[index++] = arr[i];
                    // System.out.println(index);
                    Main.numGroup(arr, i + 1, length-1, sum - arr[i]);
                }
                else	//因为后面的数比这个大，若此时temp_sum小于0，则后面的数更不满足条件，不用再进行循环
                    break;
            }
        }
        index--;
        //  System.out.println(index);
    }


    public static void main(String[] args) {
        double[] a = { 4003.4,7864.08,2912.62,582.52,1747.57,1098.06,1564.08,699.03,2330.09,5825.24,5242.72,1703.88,1456.31,150.16,36.12,2907.38,2912.61,1911.51,2446.6,2173.98,6553.4,2038.83,4368.93,7281.55,3145.63,6815.53,5906.8,2330.1,1587.82,7288.69,2941.75,2092.56,7060.19,2213.59,3786.41,873.79,2318.45,4899.03,1992.23,1125.18,291.26,1514.56,2319.9,3394.37,1403.77,2029.81,2621.36,1048.54,4375.34,449.13,2751.96,421.43,2390.1,5766.99,4083.5,203.88,3058.25,2466.99,4096.31,6116.51,1543.69,4660.19,511.31,728.16};
        int [] arr=new int[a.length];
        for (int i=0;i<a.length;i++)
        {
            arr[i]= formatDoubleTOInt(a[i],100.0);
        }
        int sum = 817182;

        //SolveProb.numGroupAll(arr, 0, arr.length, sum);//数组未排序

        Arrays.sort(arr);  //对数组进行排序后的话，可以用numGroup方法

        Main.numGroup(arr, 0, arr.length, sum);
    }
}

